package backtrack;
import java.util.*;
public class _09_90_子集Ⅱ {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
	boolean use[];
    public List<List<Integer>> subsetsWithDup(int[] nums) {
    	Arrays.sort(nums);
    	use = new boolean[nums.length];
    	backtracking(nums,0);
    	
    	return result;
    }
    
    public void backtracking(int[] nums, int index) {
    	result.add(new ArrayList<Integer>(item));
    	System.out.println(item);
    	for(int i = index; i < nums.length; i++) {
    		// 如果i-1和i相同 且 i-1已经过了（当前item不包含i-1，则跳过当前i
    		// 因为当前i的组合已经包含在i-1的组合中了，会导致有重复子集
    		// 此题与40组合总和Ⅱ很类似
    		if(i > 0 && nums[i] == nums[i-1] && use[i-1] == false) {
    			continue;
    		} 
			item.add(nums[i]);
			use[i] = true;
    		
    		backtracking(nums, i + 1);
    		item.remove(item.size() - 1);
    		use[i] = false;
    	}
    	
    }
    
    public static void main(String[] args) {
    	int[] nums = {0};
		new _09_90_子集Ⅱ().subsetsWithDup(nums);
	}
}
